﻿// 0912train02.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
//

#include <iostream>
#include <string>
#include <sstream>
#include <algorithm>
#include <limits>
#include <iomanip>
#include <vector>
#include <unordered_map>
#include <unordered_set>

using namespace std;

/*
高优先级告警产生后，低优先级告警不再产生
请根据原始告警列表和告警抑制关系，给出实际产生的告警列表。不会出现循环抑制的情况
告警不会传递，比如A->B，B->C，这种情况下A不会直接抑制C
被抑制的告警仍然可以抑制其他低优先级告警

输入描述
第一行为数字N，表示告警抑制关系个数，0 <= N <= 120  
接下来N行，每行是由空格分隔的两个告警ID，例如: id1 id2，表示id1抑制id2。
最后一行为告警产生列表，列表长度[1, 100]

输出描述
真实产生的告警列表

输入
2
A B
B C
A B C D E A A A
输出
A D E
A抑制B，故当A出现之后，B由于被抑制不再产生
由于被抑制的告警仍然可以抑制其他低优先级告警，故B虽然被抑制，但仍然可以抑制C，故C不再产生
 */
class Solution01
{
public:
    Solution01(vector<vector<string>>&linked_vec, vector<string>&exec_vec)
    {
        unordered_map<string, unordered_set<string>>linked_map;

        //key vec[1] value vec[0]
        for (auto&link_item:linked_vec)
        {
            linked_map[link_item[1]].insert(link_item[0]);
        }

        unordered_set<string>repeat_set;

        vector<string>result;
        for (auto&curr:exec_vec)
        {
            unordered_set<string>parent_set;
            if (linked_map.count(curr)>0)
            {
                parent_set = linked_map.at(curr);
            }
            if (!parent_set.empty())
            {
                bool is_find = false;
                for (auto&p_item:parent_set)
                {
                    if (repeat_set.count(p_item)>0)
                    {
                        is_find = true;
                    }
                }
                if (is_find)
                {
                    repeat_set.insert(curr);
                    continue;
                }
            }

            repeat_set.insert(curr);
            result.push_back(curr);
        }

        for (int i=0; i<result.size(); i++)
        {
            cout << result[i];
            if (i!=result.size()-1)
            {
                cout << ' ';
            }
        }
	    //Solution01
    }
};


/*
小明在直线的公路上种树，现在给定可以种树的坑位的数量和位置，以及需要种多少棵树苗，
问树苗之间的最小间距是多少时，可以保证种的最均匀（两棵树苗之间的最小间距最大）
输入
输入三行：
- 第一行一个整数：坑位的数量
- 第二行以空格分隔的数组：坑位的位置
- 第三行一个整数：需要种植树苗的数量
输出
树苗之间的最小间距

输入
7
1 3 6 7 8 11 13
3
输出
6
三颗树苗分别种在 1、7、13 的位置，可以保证种的最均匀，树苗之间的最小间距为 6
如果选择最小间距为 7，则无法种下3颗树苗
 */
class Solution02
{
public:
    Solution02(vector<int>&num_vec, int target)
    {
        if (target==1)
        {
            cout << 0;
            return;
        }

        //两颗树苗之间的间距最多max(num_vec)-min(num_vec)
        //间距最小0
        //二分法找出最小间距
        int v_size = num_vec.size();
        sort(num_vec.begin(), num_vec.end());

        int min_pos = num_vec[0], max_pos = num_vec[v_size - 1];
        int left = 0, right = max_pos - min_pos + 1;

        int result = 0;
        while (left<right)
        {
            int mid = left + (right - left) / 2;

            int prev_pos = num_vec[0];
            int count = 1;

            for (int i=1; i<num_vec.size(); i++)
            {
	            if (num_vec[i]-prev_pos>=mid)
	            {
                    count++;
                    prev_pos = num_vec[i];
	            }
            }

            if (count>=target)
            {
                result = mid;
	            //满足条件，扩大种植距离
                left = mid + 1;
            }
            else
            {
                right = mid;
            }
            //while (left<right)
        }
        cout << result;
        //Solution02
    }
};

/*
 A、B两个人玩抢7游戏，游戏规则为A先报一个起始数字X (10 <= X <= 10000），
 B报下一个数字Y，(0<X-Y<3)，A再报一个数字Z(0<Y-Z<3)，以此类推，直到其中一个抢到7，
 抢到7即为胜者，在B赢得比赛的情况下，一共有多少种组合？
 */

class Solution03
{
public:
    string add(string&str_1, string&str_2)
    {
        int length_1 = str_1.size();
        int length_2 = str_2.size();

        string result;
        int i_1 = length_1 - 1, i_2 = length_2 - 1;
        int carry = 0; //进位
        while (i_1>=0 || i_2>=0 || carry>0)
        {
            int sum = carry;
            if (i_1 >= 0)
            {
                sum += str_1[i_1] - '0';
                i_1--;
            }
            if (i_2>=0)
            {
                sum += str_2[i_2] - '0';
                i_2--;
            }
            carry = sum / 10;
            result += (sum % 10 + '0');
        }
        reverse(result.begin(), result.end());
        return result;
        //add
    }

    void solve03(int total)
    {
        if (total <= 7)
        {
            cout << 0;
            return;
        }
        if (total == 8 || total == 9 || total == 10)
        {
            cout << 1;
            return;
        }

        vector<string>dynamic_A(total + 2);
        vector<string>dynamic_B(total + 2);

        //从total开始计数，取到total只有1种办法
        dynamic_A[total] = to_string(1);

        for (int i = total - 1; i >= 7; i--)
        {
            //B从A转移而来，差值只能是1或者2
            dynamic_B[i] = add(dynamic_A[i + 1], dynamic_A[i + 2]);
            dynamic_A[i] = add(dynamic_B[i + 1], dynamic_B[i + 2]);
        }

        cout << dynamic_B[7];
    }

	Solution03(int total)
	{
        solve03(total);
        //Solution03
	}
};

class Solution13
{
public:
    vector<int> precompute_max_lengths(int m) {
        vector<int> max_len(m + 1, 0);
        max_len[7] = 1;
        max_len[8] = max_len[9] = max_len[10] = 1;
        max_len[11] = 1;
        for (int i = 12; i <= m; i++) {
            max_len[i] = max(max_len[i - 2], max(max_len[i - 3] + 1, max_len[i - 4])) + 1;
        }
        return max_len;
    }
    string add(const string& a, const string& b, string& result) {
        result.clear();
        result.reserve(max(a.length(), b.length()) + 1);

        int carry = 0;
        int i = a.length() - 1;
        int j = b.length() - 1;

        while (i >= 0 || j >= 0 || carry) {
            int sum = carry;
            if (i >= 0) sum += a[i--] - '0';
            if (j >= 0) sum += b[j--] - '0';
            carry = sum / 10;
            result.push_back(sum % 10 + '0');
        }

        reverse(result.begin(), result.end());
        return result;
    }
    string multiplyBy2(const string& num, string& result) {
        result.clear();
        result.reserve(num.length() + 1);

        int carry = 0;
        for (int i = num.length() - 1; i >= 0; i--) {
            int digit = (num[i] - '0') * 2 + carry;
            carry = digit / 10;
            result.push_back(digit % 10 + '0');
        }
        if (carry) result.push_back(carry + '0');

        reverse(result.begin(), result.end());
        return result;
    }
    Solution13(int num)
    {
        // 预分配所有需要的字符串空间
        vector<string> dp(10000 + 1);
        auto max_lengths = precompute_max_lengths(num);
        for (int i = 0; i <= num; i++) {
            dp[i].reserve(max_lengths[i]);
        }

        // 初始化
        dp[7] = "0";
        dp[8] = "1";
        dp[9] = "1";
        dp[10] = "1";
        dp[11] = "3";

        // 重用的临时字符串，避免重复创建
        string temp1, temp2;
        temp1.reserve(max_lengths[num]);
        temp2.reserve(max_lengths[num]);

        for (int k = 12; k <= num; k++) {
            // 重用临时字符串，避免创建新的
            multiplyBy2(dp[k - 3], temp1);
            add(dp[k - 2], temp1, temp2);
            add(temp2, dp[k - 4], dp[k]);
        }

        cout << dp[num];
    }
};

/*

1 1 0 0
0 0 0 1
0 0 1 1
1 1 1 1
现需要将矩阵中所有的 1 进行反转为 0，规则如下：
1. 当点击一个 1 时，该 1 被反转为 0，
同时相邻的上、下、左、右，以及左上、左下、右上、右下 8 个方向的 1 （如果存在 1）均会自动反转为 0；

2. 进一步地，一个位置上的 1 被反转为 0 时，
与其相邻的 8 个方向的 1 （如果存在 1）均会自动反转为 0。
按照上述规则示例中的矩阵只最少需要点击 2 次后，所有均值 0
请问，给定一个矩阵，最少需要点击几次后，所有数字均为 0？

输入
第一行输入两个整数，分别表示矩阵的行数 N 和列数 M，取值范围均为 [1,100]
接下来 N 行表示矩阵的初始值，每行均为 M 个数，取值范围 [0,1]
输出
输出一个整数，表示最少需要点击的次数
 */
class Solution04
{
	
};

int main()
{
	{
        int num;
        cin >> num;

        Solution03 solu(num);

        //string str_1 = "900", str_2 = "900";
        //cout << solu.add(str_1, str_2);

        return 0;
	}
    {
/*
7
1 3 6 7 8 11 13
3
*/
        int v_size;
        cin >> v_size;

        vector<int>num_vec(v_size);
        for (int i=0; i<v_size; i++)
        {
            cin >> num_vec[i];
        }

        int target;
        cin >> target;
        Solution02 solu(num_vec, target);

        return 0;
    }
/*
2
A B
B C
A B C D E
*/
    int v_size;
    cin >> v_size;
    vector<vector<string>>linked_vec(v_size);
    for (int i=0; i<v_size; i++)
    {
        vector<string>min_vec(2);
        cin >> min_vec[0] >> min_vec[1];
        linked_vec[i] = min_vec;
    }
    cin.ignore();
    vector<string>exec_vec;
    string input;
    getline(cin, input);
    stringstream oh_sstream(input);
    string token;
    while (oh_sstream>>token)
    {
        exec_vec.push_back(token);
    }
    Solution01 solu(linked_vec, exec_vec);

}

// 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
// 调试程序: F5 或调试 >“开始调试”菜单

// 入门使用技巧: 
//   1. 使用解决方案资源管理器窗口添加/管理文件
//   2. 使用团队资源管理器窗口连接到源代码管理
//   3. 使用输出窗口查看生成输出和其他消息
//   4. 使用错误列表窗口查看错误
//   5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
//   6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件
